import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;


public class processor {
	public List<Node> toTrees(String file) throws IOException {
		BufferedReader br = getBr(file);
		String line;
		List<Node> roots = new LinkedList<Node>();
		while ((line=br.readLine())!=null)
			roots.add(toTree(line));
		br.close();
		return roots;
	}
	
	private Node toTree(String line) {
		List<String> tokens = prepare(line);
		Node current = null;
		for (String s:tokens)
		{
			if (s.startsWith("("))
			{
				if (current==null)
				{
					current = new Node();
					current.parent=null;
					current.value=s.substring(1);
					current.children=new LinkedList<Node>();
				}
				else
				{
					Node temp = new Node();
					temp.parent = current;
					temp.value = s.substring(1);
					temp.children=new LinkedList<Node>();
					if (current.children==null)
						current.children=new LinkedList<Node>();
					current.children.add(temp);
					current = temp;
				}
			}
			else if (!s.equals(")"))
			{
				current.terminal=s;
			}
			else
			{
				if (current.parent!=null)
					current=current.parent;
			}
		}
		return current;
	}

	private List<String> prepare(String line) {
		String pline = line.trim();
		String[] tokens = pline.split(" ");
		System.out.println(line);
		List<String> result = new LinkedList<String> ();
		for (String s:tokens)
		{
			if (s.startsWith("("))
				result.add(s);
			else
			{
				int first = s.indexOf(")");
				result.add(s.substring(0, first));
				for (int i=first;i<s.length();i++)
					result.add(")");
			}
		}
		return result;
	}
	
	public BufferedReader getBr(String file) throws FileNotFoundException {
		return new BufferedReader(new FileReader(file));
	}
	
	public String printTree(Node root)
	{
		String result="";
		if (root.children!=null && root.children.size()!=0)
		{
			result = result + "(" + root.value;
			for (Node child : root.children)
				result = result + " " + printTree(child);
			result = result + ")";
		}
		else
			result = result + "(" + root.value + " " + root.terminal + ")";
		return result;
	}
	
	public Gcount learnCount(List<Node> trees) 
	{
		Gcount gcount = new Gcount();
		for (Node root:trees)
			learnCount(root, gcount);
		return gcount;
	}
	
	public void learnCount(Node root, Gcount gcount) {
		if (root.children==null || root.children.size() == 0)
		{
			gcount.terminals.add(root.terminal);
			gcount.tags.add(root.value);
		}
		else
		{
			gcount.tags.add(root.value);
			for (Node child:root.children)
				learnCount(child, gcount);
		}
	}
	
	public Grammar learn(Gcount gcount)
	{
		Grammar grammar = new Grammar();
		for (String s:gcount.tags)
		{
			grammar.tags.add(s);
		}
		for (String nt:gcount.tags)
		{
			for (String t:gcount.terminals)
				grammar.t_rules.put(nt + "|" + t, 0d);
		}
		for (String nt1:gcount.tags)
		{
			for (String nt2:gcount.tags)
			{
				for (String nt3:gcount.tags)
					grammar.s_rules.put(nt1 + "|" + nt2 + " " + nt3, 0d);
			}
		}
		return grammar;
	}
	
	public void printGrammar(Grammar grammar, String file) throws IOException
	{
		BufferedWriter bw = new BufferedWriter(new FileWriter(file));
		for (String s:grammar.tags)
		{
			for (String t:grammar.s_rules.keySet())
			{
				String[] tokens = t.split("\\|");
				if (tokens[0].equals(s))
				{	
					System.out.println(tokens[0] + " -> " + tokens[1] + " # " + grammar.s_rules.get(t));
					bw.write(tokens[0] + " -> " + tokens[1] + " # " + grammar.s_rules.get(t));
					bw.newLine();
				}
			}
			for (String t:grammar.t_rules.keySet())
			{
				String[] tokens = t.split("\\|");
				if (tokens[0].equals(s))
				{	
					System.out.println(tokens[0] + " -> " + tokens[1] + " # " + grammar.t_rules.get(t));
					bw.write(tokens[0] + " -> " + tokens[1] + " # " + grammar.t_rules.get(t));
					bw.newLine();
				}
			}
		}
		bw.close();	
	}
	
	private void prepareDev(Gcount gcount, String dev, String devunk) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader(dev));
		BufferedWriter bw = new BufferedWriter(new FileWriter(devunk));
		String line;
		while((line=br.readLine())!=null)
		{
			line=line.trim();
			String[] tokens = line.split(" ");
			for (int i=0; i<tokens.length; i++)
			{
				if (!gcount.terminals.contains(tokens[i]))
				{	
					tokens[i] = "<unk>";
				}
			}
			String out ="";
			for (int i=0; i<tokens.length; i++)
				out = out + tokens[i] + " ";
			out = out.substring(0, out.length()-1);
			bw.write(out);
			bw.newLine();
		}
		bw.close();
		br.close();	
	}
	
	public String[] getWords(Node root)
	{
		List<String> words = new LinkedList<String> ();
		getWord(root,words);
		return words.toArray(new String[0]);
	}
	
	public List<String[]> getWords(String file) throws IOException
	{
		BufferedReader br = new BufferedReader(new FileReader(file));
		String line;
		List<String[]> listwords = new LinkedList<String[]> ();
		while((line=br.readLine())!=null)
		{
			String[] words = line.split(" ");
			String[] words1 = new String[words.length];
			for (int i=0; i<words.length; i++)
				words1[i] = words[i];
			listwords.add(words1);
		}
		br.close();
		return listwords;
	}

	private void getWord(Node root, List<String> words) {
		if (root.terminal!=null)
			words.add(root.terminal);
		else
		{
			for (Node child:root.children)
				getWord(child,words);
		}
	}
	
	public Node parse(String[] words, Grammar grammar, HashSet<String> wordTypes)
	{
			Parser parser = new Parser();
			parser.s_rules = new HashMap<String, Double>();
			parser.t_rules = new HashMap<String, Double>();
			for (String s:grammar.s_rules.keySet())
				parser.s_rules.put(s, grammar.s_rules.get(s));
			for (String s:grammar.t_rules.keySet())
				parser.t_rules.put(s, grammar.t_rules.get(s));
			parser.tags = grammar.tags.toArray(new String[0]);
			parser.words = words;
			parser.tagsCount = parser.tags.length;
			parser.wordsCount = words.length;
			parser.wordTypes = wordTypes;
			parser.prepare();
			parser.initialize();
			parser.parse("train");
			Node root = parser.getTree(0, parser.wordsCount, "TOP", null);
			return root;
	}
	
	public void maximize(Grammar grammar, Node gold, Node parse)
	{
		double eata=0.3d;
		HashMap<String, Double> delta_t_rules = new HashMap<String, Double>();
		HashMap<String, Double> delta_s_rules = new HashMap<String, Double>();
		for (String s:grammar.t_rules.keySet())
			delta_t_rules.put(s, 0.0d);
		for (String s:grammar.s_rules.keySet())
			delta_s_rules.put(s, 0.0d);
		plusGold(gold, delta_t_rules, delta_s_rules);
		minusParse(parse, delta_t_rules, delta_s_rules);
		for (String s:grammar.t_rules.keySet())
			grammar.t_rules.put(s,grammar.t_rules.get(s) + eata*delta_t_rules.get(s));
		for (String s:grammar.s_rules.keySet())
			grammar.s_rules.put(s, grammar.s_rules.get(s) + eata*delta_s_rules.get(s));
	}

	private void minusParse(Node parse, HashMap<String, Double> delta_t_rules,
			HashMap<String, Double> delta_s_rules) {
		if (parse.terminal!=null)
			delta_t_rules.put(parse.value + "|" + parse.terminal, delta_t_rules.get(parse.value + "|" + parse.terminal) - 1);
		else
		{	
			delta_s_rules.put(parse.value + "|" + parse.children.get(0).value + " " + parse.children.get(1).value, delta_s_rules.get(parse.value + "|" + parse.children.get(0).value + " " + parse.children.get(1).value) - 1);
			minusParse(parse.children.get(0), delta_t_rules, delta_s_rules);
			minusParse(parse.children.get(1), delta_t_rules, delta_s_rules);
		}
		
	}

	private void plusGold(Node gold, HashMap<String, Double> delta_t_rules,
			HashMap<String, Double> delta_s_rules) {
		if (gold.terminal!=null)
			delta_t_rules.put(gold.value + "|" + gold.terminal, delta_t_rules.get(gold.value + "|" + gold.terminal) + 1);
		else
		{	
			delta_s_rules.put(gold.value + "|" + gold.children.get(0).value + " " + gold.children.get(1).value, delta_s_rules.get(gold.value + "|" + gold.children.get(0).value + " " + gold.children.get(1).value) + 1);
			plusGold(gold.children.get(0), delta_t_rules, delta_s_rules);
			plusGold(gold.children.get(1), delta_t_rules, delta_s_rules);
		}
		
	}
	
	public HashSet<String> wordTypes(List<Node> gold)
	{
		HashSet<String> wordTypes = new HashSet<String> ();
		for (Node root:gold)
			wordTypes(root, wordTypes);
		return wordTypes;
	}

	private void wordTypes(Node root, HashSet<String> wordTypes) {
		if (root.terminal!=null)
			wordTypes.add(root.terminal);
		else
		{
			for (Node child:root.children)
				wordTypes(child, wordTypes);
		}
	}
	
	public Node binary(Node root, int mode)
	{
		if (root.children==null || root.children.size()==0)
		{}
		else if (root.children.size()==1)
		{	binary(root.children.get(0), mode);}
		else if (root.children.size()==2)
		{
			binary(root.children.get(0), mode);
			binary(root.children.get(1), mode);
		}
		else
		{
			if (root.value.startsWith("NP") && (root.children.get(0).value.equals("DT")||root.children.get(0).value.equals("JJ")||root.children.get(0).value.equals("JJS")||root.children.get(0).value.equals("CD")||root.children.get(0).value.equals("NN")))
			{
				Node newnode = new Node();
				newnode.parent = root;
				if (mode==1)
				{
					if (root.value.endsWith("*"))
						newnode.value=root.value;
					else
						newnode.value=root.value+"*";
				}
				if (mode==2)
				{
					if (root.value.indexOf("@")>0)
					{
						String[] tokens = root.value.split("@");
						newnode.value = tokens[0]+"@"+root.children.get(0).value;
					}
					else
						newnode.value = root.value+"@"+root.children.get(0).value;
				}
				//newnode.value = root.value;
				newnode.children = new LinkedList<Node>();
				int size=root.children.size();
				for (int i=1;i<size;i++)
				{
					Node temp = root.children.remove(1);
					temp.parent = newnode;
					newnode.children.add(temp);
				}
				root.children.add(newnode);
				binary(newnode, mode);
				binary(root.children.get(0), mode);
			}
			else if (root.value.startsWith("SQ"))
			{
				Node newnode = new Node();
				newnode.parent = root;
				if (mode==1)
				{
					if (root.value.endsWith("*"))
						newnode.value=root.value;
					else
						newnode.value=root.value+"*";
				}
				if (mode==2)
				{
					if (root.value.indexOf("@")>0)
					{
						String[] tokens = root.value.split("@");
						newnode.value = tokens[0]+"@"+root.children.get(0).value;
					}
					else
						newnode.value = root.value+"@"+root.children.get(0).value;
				}
				//newnode.value = root.value;
				newnode.children = new LinkedList<Node>();
				int size=root.children.size();
				for (int i=1;i<size;i++)
				{
					Node temp = root.children.remove(1);
					temp.parent=newnode;
					newnode.children.add(temp);
				}
				root.children.add(newnode);
				binary(newnode, mode);
				binary(root.children.get(0), mode);
			}
			else if (root.value.startsWith("VB"))
			{
				Node newnode = new Node();
				newnode.parent = root;
				if (mode==1)
				{
					if (root.value.endsWith("*"))
						newnode.value=root.value;
					else
						newnode.value=root.value+"*";
				}
				if (mode==2)
				{
					if (root.value.indexOf("@")>0)
					{
						String[] tokens = root.value.split("@");
						newnode.value = tokens[0]+"@"+root.children.get(0).value;
					}
					else
						newnode.value = root.value+"@"+root.children.get(0).value;
				}
				//newnode.value = root.value;
				newnode.children = new LinkedList<Node>();
				int size=root.children.size();
				for (int i=1;i<size;i++)
				{
					Node temp = root.children.remove(1);
					temp.parent=newnode;
					newnode.children.add(temp);
				}
				root.children.add(newnode);
				binary(newnode, mode);
				binary(root.children.get(0), mode);
			}
			else
			{
				int size=root.children.size();
				Node newnode = new Node();
				newnode.parent = root;
				if (mode==1)
				{
					if (root.value.endsWith("*"))
						newnode.value=root.value;
					else
						newnode.value=root.value+"*";
				}
				if (mode==2)
				{
					if (root.value.indexOf("@")>0)
					{
						String[] tokens = root.value.split("@");
						newnode.value = tokens[0]+"@"+root.children.get(0).value;
					}
					else
						newnode.value = root.value+"@"+root.children.get(0).value;
				}
				//newnode.value = root.value+"@"+root.children.get(size-1).value;
				//newnode.value = root.value;
				newnode.children = new LinkedList<Node>();
				
				for (int i=1;i<size;i++)
				{
					Node temp = root.children.remove(1);
					temp.parent=newnode;
					newnode.children.add(temp);
				}
				root.children.add(newnode);
				binary(newnode, mode);
				binary(root.children.get(0), mode);
			}
		}
		return root;
	}
	
	public Node head(Node root)
	{
		if (root.children==null || root.children.size()==0)
			root.value = root.value + "@" + root.terminal;
		else
		{
			//System.out.println(root.value + root.children.size());
			head(root.children.get(0));
			head(root.children.get(1));
			if (root.value.startsWith("NN") || root.value.startsWith("NP") || root.value.startsWith("NX"))
			{
				if (root.children.get(1).value.startsWith("NN") || root.children.get(1).value.startsWith("NP"))
				{
					String[] tokens = root.children.get(1).value.split("@");
					root.value = root.value + "@" + tokens[1];
				}
				else if (root.children.get(0).value.startsWith("NN") || root.children.get(0).value.startsWith("NP") || root.value.startsWith("NX"))
				{
					String[] tokens = root.children.get(0).value.split("@");
					root.value = root.value + "@" + tokens[1];
				}
				else
				{
					String[] tokens = root.children.get(1).value.split("@");
					//System.out.println(root.children.get(1).value);
					root.value = root.value + "@" + tokens[1];
				}
			}
			else if (root.value.startsWith("VP")||root.value.startsWith("VB"))
			{
				if (root.children.get(0).value.startsWith("VB") || root.children.get(0).value.startsWith("VP"))
				{
					String[] tokens = root.children.get(0).value.split("@");
					root.value = root.value + "@" + tokens[1];
				}
				else if (root.children.get(1).value.startsWith("VB") || root.children.get(1).value.startsWith("VP"))
				{
					String[] tokens = root.children.get(1).value.split("@");
					root.value = root.value + "@" + tokens[1];
				}
				else
				{
					String[] tokens = root.children.get(0).value.split("@");
					root.value = root.value + "@" + tokens[1];
				}
			}
			else if (root.value.startsWith("PP"))
			{
				String[] tokens = root.children.get(0).value.split("@");
				root.value = root.value + "@" + tokens[1];
			}
			else if (root.value.equals("SQ")||root.value.equals("X"))
			{
				//System.out.println(root.children.get(0).value);
				String[] tokens = root.children.get(0).value.split("@");
				root.value = root.value + "@" + tokens[1];
			}
			else if (root.value.startsWith("ADJP"))
			{
				
					String[] tokens = root.children.get(0).value.split("@");
					root.value = root.value + "@" + tokens[1];
			}
			else
			{
				String[] tokens = root.children.get(0).value.split("@");
				root.value = root.value + "@" + tokens[1];
			}
		}
		return root;
	}
	public Node unary(Node root, int mode)
	{
		if (root.children==null || root.children.size()==0)
		{}
		else if (root.children.size()>1)
		{
			for (Node child:root.children)
				unary(child, mode);
		}
		else 
		{
			unary(root.children.get(0), mode);
			if (root.children.get(0).children==null || root.children.get(0).children.size()==0)
			{
				root.value = root.value + "_" + root.children.get(0).value;
				root.terminal = root.children.get(0).terminal;
				root.children=null;
			}
			else
			{
				Node child = root.children.get(0);
				root.value = root.value + "_" + root.children.get(0).value;
				root.children=new LinkedList<Node>();
				for (Node n:child.children)
				{
					unary(n, mode);
					root.children.add(n);
					n.parent=root;
				}
			}
		}
		return root;
	}

	private void preprocess(String file, List<Node> roots, int mode) throws IOException {
		
		BufferedWriter bw = new BufferedWriter(new FileWriter(file));
		
		for (Node root:roots)
		{
			if (mode==1 || mode==2)
			{
				binary(root, mode);
				unary(root, mode);
			}
			else if (mode==3)
			{
				binary(root, 1);
				unary(root, 1);
				head(root);
			}
			String out = printTree(root);
			System.out.println(printTree(root));
			bw.write(out);
			bw.newLine();
		}
		bw.close();
	}



}
